public class Test01 {
    private int[] tmp;
    public int reversePairs(int[] record) {
        tmp = new int[record.length];
        int count = mergerSort(record, 0, record.length - 1);
        return count;
    }

    private int mergerSort(int[] num, int l, int r){
        if(l >= r) return 0;
        int ret = 0;
        int mid = l + (r - l) / 2;
        ret += mergerSort(num, l, mid);
        ret += mergerSort(num, mid+1, r);
        //统计本次归并，在一左，一右情况下可以产生的逆序对
        int cur1 = l, cur2 = mid + 1, i = 0;
        while(cur1 <= mid && cur2 <= r){
            if(num[cur1] <= num[cur2]) tmp[i++] = num[cur1++];
            else {ret += mid - cur1 + 1; tmp[i++] = num[cur2++];}
        }
        //处理没有合并完的情况
        while(cur1 <= mid) tmp[i++] = num[cur1++];
        while(cur2 <= r) tmp[i++] = num[cur2++];
        //将tmp数组中的元素，放到原来的数组，完成排序
        for(int j = l ; j <= r; j++){
            num[j] = tmp[j-l];
        }
        return ret;
    }
}
